package 剑指offer;

public class 剑指Offer53在排序数组中查找数字 {
    public static void main(String[] args) {
        int[] arr = new int[]{5,7,7,8,8,10};
        System.out.println(search(arr, 8));

    }
    //方式1：遍历
    public static int search(int[] nums, int target) {
        int count = 0;
        for (int i: nums) {
            if (i == target) {
                count++;
            }
        }
        return count;
    }
    //方式二：先二分早遍历
    public int search1(int[] arr, int target) {
        //先二分，再查找目标元素
        int left = 0;
        int right = arr.length - 1;
        int count = 0;
        while(left <= right){
            int mid = (left + right) >> 1;
            if(arr[mid] == target){
                // count = 1;
                for(int i = mid;i < arr.length;i++){
                    if(arr[i] != target){
                        break;
                    }
                    count++;
                }
                for(int i = mid-1 ; i >= 0;i--){
                    if(arr[i] != target){
                        break;
                    }
                    count++;
                }
                break;
            }else if(arr[mid] < target){
                left = mid + 1;
            }else{
                right = mid-1;
            }
        }
        return count;
    }
}

